ABSTRACT
The spread of an epidemic is often modeled by an SIR random process on a social network graph. The MININFEDGE problem for optimal social distancing involves minimizing the expected number of infections, when we are allowed to break at most B edges;similarly the MININFNODE problem involves removing at most B vertices. These are fundamental problems in epidemiology and network science. While a number of heuristics have been considered, the complexity of these problems remains generally open. In this paper, we present two bicriteria approximation algorithms for MININFEDGE, which give the first non-trivial approximations for this problem. The first is based on the cut sparsification result of Karger (1999), and works when the transmission probabilities are not too small. The second is a Sample Average Approximation (SAA) based algorithm, which we analyze for the Chung-Lu random graph model. We also extend some of our results to tackle the MININFNODE problem.